#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//81
// class Solution {
// public:
//     bool search(vector<int>& nums, int target) 
//     {
//         sort(nums.begin(),nums.end());
//         int left=0;
//         int right=(int)(nums.size())-1;
//         int mid=left+((right-left)/2);
//         while(left<=right)
//         {
//             if(nums[mid]==target)
//                 return true;
//             else if(nums[mid]<target)
//             {
//                 left=mid+1;
//                 mid=left+((right-left)/2);
//             }
//             else
//             {
//                 right=mid-1;
//                 mid=left+((right-left)/2);
//             }
//         }
//         return false;
//     }
// };
//33
class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        sort(nums.begin(),nums.end());
        int left=0;
        int right=(int)(nums.size())-1;
        int mid=left+((right-left)/2);
        while(left<=right)
        {
            if(nums[mid]==target)
                return mid;
            else if(nums[mid]<target)
            {
                left=mid+1;
                mid=left+((right-left)/2);
            }
            else
            {
                right=mid-1;
                mid=left+((right-left)/2);
            }
        }
        return -1;
    }
};
int main()
{
    vector<int> v={4,5,6,7,0,1,2};
    Solution().search(v,0);
    //cout<<ret<<endl;
    return 0;
}